#include<iostream>
#include<utility> //pair
#include<string>
#include<vector>
#include<assert.h>
#include<time.h>

using namespace std;

enum Colour
{
	RED,
	BLACK
};

//      pair<K. V>
template<class T>
struct RBTreeNode //成员都要在类外访问，用struct
{
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	Colour _col;
	T _data;

	RBTreeNode(const T& data)
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(RED)
		, _data(data)
	{}
};

//             T        T&         T*        
template<class T, class Ref, class Ptr>
struct RBTreeItreator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeItreator<T, Ref, Ptr> Self;

	Node* _node;

	RBTreeItreator(Node* node)
		: _node(node)
	{}

	//operator->
	Ptr operator->()
	{
		return &_node->_data;
	}
	//operator*
	Ref operator*()
	{
		return _node->_data;
	}	
	//operator++
	Self operator++()
	{
		//左--->中--->右
		//右不为空，访问其右子树最左节点
		//右为空，该子树已经访问完了，沿路径向上寻找
		//                            父亲为空 ---> 该树已经访问完了，让迭代器指向end()
		//                            我是父亲的左 ---> 访问父亲
		//                            我是父亲的右 ---> 父亲这颗子树也已经访问完了，继续向上寻找
		Node* cur = _node;
		Node* parent = nullptr;

		assert(cur);

		if (cur->_right)
		{
			cur = cur->_right;
			while (cur->_left)
			{
				cur = cur->_left;
			}

			_node = cur; //改变该迭代器本身
		}
		else
		{
			parent = cur->_parent;

			//如果cur是parent的右会进入循环，并沿路径向上找，直到cur为parent的左或者parent为空，然后跳出循环
			while (parent && cur == parent->_right)
			{
				cur = parent;
				parent = parent->_parent;
			}
			
			_node = parent;
		}

		return *this; //返回该迭代器，直接传值返回		
	}
	//operatpr--
	Self& operator--()
	{
		Node* cur = _node;
		Node* parent = nullptr;

		assert(cur);

		if (cur->_left)
		{
			cur = cur->_left;
			while (cur->_right)
			{
				cur = cur->_right;
			}
			_node = cur; //改变该迭代器本身

			return *this; //返回该迭代器
		}
		else
		{
			parent = cur->_parent;
			while (parent && cur == parent->_left)
			{
				cur = parent;
				parent = parent->_parent;
			}

			_node = parent;
			return *this;
		}
	}
	//operator==
	bool operator==(const Self& right) //第一个参数默认为this
	{
		return _node == right._node;
	}
	//operator!=
	bool operator!=(const Self& right) 
	{
		return _node != right._node;
	}
};

// set  RBTree<K, K, SetKeyOfT>
// map  RBTree<K, pair<K, V>, MapKeyOfT>
template<class K, class T, class KeyOfT>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	typedef RBTreeItreator<T, T&, T*> iterator;
	typedef RBTreeItreator<T, const T&, const T*> const_iterator;

	RBTree()
		: _root(nullptr)
	{}

	//左单旋
	void RotateL(Node* root)
	{
		Node* Pparent = root->_parent;

		Node* rootR = root->_right;
		Node* rootRL = rootR->_left;

		root->_right = rootR->_left;
		if (rootRL)
			rootRL->_parent = root;

		rootR->_left = root;
		root->_parent = rootR;

		//root->_bf = rootR->_bf = 0;
		//if(rootRL)
		//	rootRL->_bf = 0;

		if (root == _root)
		{
			_root = rootR;
			_root->_parent = nullptr;
		}
		else
		{
			if (Pparent->_left == root)
			{
				Pparent->_left = rootR;
				rootR->_parent = Pparent;
			}
			else if (Pparent->_right == root)
			{
				Pparent->_right = rootR;
				rootR->_parent = Pparent;
			}
			else
			{
				assert(false);
			}
		}
	}
	//右单旋
	void RotateR(Node* root)
	{
		Node* Pparent = root->_parent;

		Node* rootL = root->_left;
		Node* rootLR = rootL->_right;

		root->_left = rootL->_right;
		if (rootLR)
			rootLR->_parent = root;

		rootL->_right = root;
		root->_parent = rootL;

		//root->_bf = rootL->_bf = 0;
		//if(rootLR)
		//	rootLR->_bf = 0;

		if (root == _root)
		{
			_root = rootL;
			_root->_parent = nullptr;
		}
		else
		{
			if (Pparent->_left == root)
			{
				Pparent->_left = rootL;
				rootL->_parent = Pparent;
			}
			else if (Pparent->_right == root)
			{
				Pparent->_right = rootL;
				rootL->_parent = Pparent;
			}
			else
			{
				assert(false);
			}
		}
	}
	//插入
	pair<iterator, bool> insert(const T& data)
	{
		KeyOfT kot;

		//第一次插入
		if (_root == nullptr)
		{
			_root = new Node(data);
			//根节点置黑
			_root->_col = BLACK;
			return make_pair(iterator(_root), true);
		}
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (kot(data) < kot(cur->_data))
			{
				//往左走
				parent = cur;
				cur = cur->_left;
			}
			else if (kot(data) > kot(cur->_data))
			{
				//往右走
				parent = cur;
				cur = cur->_right;
			}
			else //相等
			{
				return make_pair(iterator(cur), false);
			}
		}
		//找到位置
		cur = new Node(data);
		if (kot(data) < kot(parent->_data))
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;

		//开始检查红黑树性质是否遭到破坏

		Node* newNode = cur; //提前记录要返回的iterator
		//如果parent为黑，插入完成
		if (parent->_col == BLACK)
		{
			return make_pair(iterator(cur), true);
		}
		//如果parent为红，开始调整
		else
		{
			while (cur->_parent && cur->_parent->_col == RED) //如果parent为红，开始调整
			{
				//根据cur重置parent、grandparent、uncle
				parent = cur->_parent;
				Node* grandparent = parent->_parent;
				Node* uncle = nullptr;
				if (parent == grandparent->_left)
				{
					uncle = grandparent->_right;
				}
				else
				{
					uncle = grandparent->_left;
				}

				//情况一
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandparent->_col = RED;

					//grandparent作cur，继续向上调整
					cur = grandparent;
				}
				//情况二、三
				else //uncle不存在/uncle为黑
				{
					//情况二 单旋					 
					//       g
					//    p
					// c
					if (parent == grandparent->_left && cur == parent->_left)
					{
						RotateR(grandparent);
						//变色
						parent->_col = BLACK;
						grandparent->_col = RED;
						break;
					}
					// g
					//    p
					//       c
					else if (parent == grandparent->_right && cur == parent->_right)
					{
						RotateL(grandparent);
						//变色
						parent->_col = BLACK;
						grandparent->_col = RED;
						break;
					}

					//情况三 双旋					 
					//    g
					// p
					//    c
					else if (parent == grandparent->_left && cur == parent->_right)
					{
						RotateL(parent);
						RotateR(grandparent);
						//变色
						cur->_col = BLACK;
						grandparent->_col = RED;
						break;
					}
					// g
					//    p
					// c
					else if (parent == grandparent->_right && cur == parent->_left)
					{
						RotateR(parent);
						RotateL(grandparent);
						//变色
						cur->_col = BLACK;
						grandparent->_col = RED;
						break;
					}
					else
					{
						assert(false);
					}
				}
			}
		}

		//根节点置黑
		_root->_col = BLACK;
		return make_pair(iterator(newNode), true);
	}
	//begin
	iterator begin()
	{
		Node* cur = _root;
		while (cur && cur->_left)
		{
			cur = cur->_left;
		}
		return iterator(cur);
	}
	//end
	iterator end()
	{
		return iterator(nullptr);
	}
	//拷贝构造
	RBTree(const RBTree<K, T, KeyOfT>& t)
	{
		_root = Copy(t._root);
	}
	//赋值重载
	RBTree<K, T, KeyOfT>& operator=(RBTree<K, T, KeyOfT> t)
	{
		swap(_root, t._root);
		return *this;
	}
	//析构
	~RBTree()
	{
		Destory(_root);
		_root = nullptr;
	}
	//Find
	iterator Find(const K& key)
	{
		Node* cur = _root;
		KeyOfT kot;
		//左走 left
		while (cur)
		{
			//右走 right
			if (kot(cur->_data) < key)
			{
				cur = cur->_right;
			}
			//左走 left
			else if (kot(cur->_data) > key)
			{
				cur = cur->_left;
			}
			//相等 ==
			else
			{
				return iterator(cur);
			}
		}
		return end();
	}

private:
	Node* Copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;

		//处理
		Node* newNode = new Node(root->_data); // T
		newNode->_col = root->_col; // col
		newNode->_left = Copy(root->_left); // left
		newNode->_right = Copy(root->_right); // right

		if (newNode->_left)
			newNode->_left->_parent = newNode; // parent
		if (newNode->_right)
			newNode->_right->_parent = newNode;

		return newNode;
	}

	void Destory(Node* root)
	{
		if (root == nullptr)
			return;

		Destory(root->_left);
		Destory(root->_right);
		delete root;
	}

	Node* _root;
};